A Look Back At Bitlayer's Efforts On BitVM
12 Nov 2024
This week Bitlayer contributed a manual SNARK verifier chunker to BitVM open source, which we believe will fill in the last missing piece of a complete BitVM implementation. Next, we are going to build a BTC bridge with an honest-minority trust assumption, based on BitVM open source.
Our contributions began with a SHA256 emulation in BitVM, which helped calculate the weight of a Bitcoin block header. Bitlayer cryptographer Andrew delivered the initial version, which was then significantly improved by other teams.
At that point, we realized that to build a practical BitVM implementation, we must:
🔸Minimize the size of the monolithic SNARK verifier
🔸Cut the monolithic verifier script into a minimal number of chunks
BitVM Achieves Major Breakthrough: SNARK Verifier Size Reduced from 7.4GB to 1GB
After half a year of hard work, the BitVM community completed the first SNARK verifiers that had the potential to run on Bitcoin, but only after some major optimizations. The initial script size, however, was 7.4 GB, way beyond what a Bitcoin block can digest (even after chunked into pieces).
Andrew proposed an optimization based on batched multiple scalar multiplication (MSM), which reduced script size from 7.4 GB to 5.6 GB.
The community kept on working, including pairing optimization based on the “On Proving Pairing” paper, multiplication optimization based on TMUL, etc. The outcome was exciting: a much smaller 1.25 GB script.
Last month, the Bitlayer cryptography team contributed a new MSM implementation with affine coordinates for both non-hinted and hinted cases, reducing the Groth16 verifier size from 1.25 GB to nearly 1 GB.
We believe it’s totally possible to reduce the size to less than 1 GB, but it definitely will take more effort than prior works.
Exploring Chunker Optimization: From Automatic to Manual Approaches in BitVM
Now let’s focus on the chunker part. The community’s first attempt was an automatic chunker contributed by Andrew, based on runtime stack analysis. However, that chunker seems impractical because the stacks reserved for intermediate values were too deep to transfer from one chunk to the next, and the hasher was way too large after employing the commit-after-hash trick.
Before we invest more resources on automatic chunker, a manual approach may be more feasible at this moment.
This week, Andrew and Freddie from Bitlayer contributed a manual chunker which may solve the aforementioned problems. Hats off to Andrew and Freddie!
The Approach Andrew and Freddie Took
(1) Standard procedure. Each chunk is a three-stage procedure: check the input hash, execute the chunk, and then check the output hash. To remove redundancy in input and output, a framework is designed to filter out unused input and output.
(2) Modular design. Manual chunker carefully divides the monolithic verifier script into logical parts, including MSM, G2 group non-fixed point checking, Miller loop accumulating (for hint comparison). For the chunks of each logical part, only minimal inputs and outputs are hashed and committed.
(3) Fine tuning. By selecting the appropriate granularity of input and output for each chunk, for instance, input by Fq or Fq12, we can make ASSERT transaction and DISPROVE transaction more balanced thereby attaining a global optimum solution for the transaction graph.
So Where are We?
- monolithic script size: 1.05 GB
- number of chunks: 975
- number of intermediate values: 1079
- size of Assert transaction: 3.6 MB
- size of Disprove transaction: 3.7 MB
What do these numbers mean? The size of each transaction in the BitVM transaction graph will be small enough to run on Bitcoin. It seems that a practical BitVM bridge is just around the corner.
What Comes Next?
Generally, we are continuing optimizing both the monolithic script size and the chunker, to further lower on-chain costs for the challenger and capital costs for the BitVM operator. Here are a few TODOs:
(1) Merge adjacent chunks specifically for MSM and non-fixed point checking
(2) Pick up the work on the automatic chunker to ease the engineering efforts
Bitlayer will keep contributing to BitVM community and the commitment will be dedicated and long-term.
Meanwhile, Bitlayer has also put a lot of effort into dispute resolution protocol design and zkVM engineering. Combining these works and the power of BitVM open source, Bitlayer will deliver a BitVM bridge testnet by the end of 2024. Stay tuned!
Follow us to stay updated on everything Bitlayer:
